package J3_27;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class test {



    //以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> ret = new ArrayList<>();

        ret.add(intervals[0]);

        for (int i = 1; i < len; i++) {
            int l = ret.get(ret.size() - 1)[0], r = ret.get(ret.size() - 1)[1];
            if (intervals[i][0] > r) {
                ret.add(intervals[i]);
            }else {
                int max = Math.max(r, intervals[i][1]);
                ret.get(ret.size() - 1)[1] = max;
            }
        }

        return ret.toArray(new int[ret.size()][]);
    }

    //给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
    //
    //你需要将 ranges 分成 两个 组（可以为空），满足：
    //
    //每个区间只属于一个组。
    //两个有 交集 的区间必须在 同一个 组内。
    //如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
    //
    //比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。
    //请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。
    public static int countWays(int[][] ranges) {
        int len = ranges.length;
        if (len == 1) {
            return 2;
        }
        List<int[]> list = new ArrayList<>();

        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

        list.add(ranges[0]);

        for (int i = 1; i < len; i++) {
            int r = list.get(list.size() - 1)[1];
            if (ranges[i][0] > r) {
                list.add(ranges[i]);
            } else {
                list.get(list.size() - 1)[1] = Math.max(r, ranges[i][1]);
            }
        }

        int n = list.size();
        int ret = 1;
        int mod = (int)1e9 + 7;
        long num = 2;
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = (int)(ret * num % mod);
            }
            n >>= 1;
            num = num * num % mod;
        }
        return ret;
        /*while (n > 0) {
            ret = ret * 2 %mod;
            n--;
        }
        return ret;*/
    }

    public static void main(String[] args) {
        int[][] intervals = {
                {57,92},{139,210},{306,345},{411,442},{533,589},{672,676},{801,831},{937,940},
                {996,1052},{1113,1156},{1214,1258},{1440,1441},{1507,1529},{1613,1659},{1773,1814},
                {1826,1859},{2002,2019},{2117,2173},{2223,2296},{2335,2348},{2429,2532},{2640,2644},
                {2669,2676},{2786,2885},{2923,2942},{3035,3102},{3177,3249},{3310,3339},{3450,3454},
                {3587,3620},{3725,3744},{3847,3858},{3901,3993},{4100,4112},{4206,4217},{4250,4289},
                {4374,4446},{4510,4591},{4675,4706},{4732,4768},{4905,4906},{5005,5073},{5133,5142},
                {5245,5309},{5352,5377},{5460,5517},{5569,5602},{5740,5791},{5823,5888},{6036,6042},
                {6096,6114},{6217,6262},{6374,6394},{6420,6511},{6564,6587},{6742,6743},{6797,6877},
                {6909,6985},{7042,7117},{7141,7144},{7276,7323},{7400,7456},{7505,7557},{7690,7720},
                {7787,7800},{7870,7880},{8013,8031},{8114,8224},{8272,8328},{8418,8435},{8493,8537},
                {8600,8704},{8766,8812},{8839,8853},{9032,9036},{9108,9189},{9222,9291},{9344,9361},
                {9448,9502},{9615,9673},{9690,9800},{9837,9868},{85,96},{145,202},{254,304},{372,411},
                {534,551},{629,692},{727,787},{861,944},{1041,1084},{1133,1174},{1260,1307},{1339,1358},
                {1478,1548},{1580,1618},{1694,1814},{1848,1891},{1936,1990},{2058,2130}
        };
        int i = countWays(intervals);
        System.out.println(i);
    }
}
